package BackTrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 1 if上卡
 *   下for
 *
 * 2 草图：
 *      i
 *      if
 *      体  for内其中一个循环体
 *      sI  下层参
 * -> 一定手动按代码跑一遍画成图（递归很难知道图上各个变量对应位置）
 *
 * 3 for内 返回用continue 不return
 */
public class 分割回文串131 {
    List<List<String>> res = new ArrayList<>();
    List<String> tmp = new ArrayList<>();
    String s;
    int n;
    public List<List<String>> partition(String s) {
        this.s = s;
        n = s.length();
        backTrack(0);
        return res;
    }
    boolean isHW(String s){
        if(s.equals("")){
            return false;
        }
        char[] cs = s.toCharArray();
        for (int i = 0; i <= cs.length/2; i++) {
            if(cs[i] != cs[cs.length-1-i]){
                return false;
            }
        }
        return true;
    }
    void backTrack(int startIndex){
        if(startIndex == n){
            //为什么N收集 -> 这样不用con，用return。
            //Fcur 内部算好 （下一个是N收集） 或者Fcur算好 if==n-1 con 【 不能r r必须N
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = startIndex+1; i <= n; i++) {
            String cur = s.substring(startIndex, i);
            if(!isHW(cur)){
                continue; // 剪枝（if! 或者 con ） 【 不可以r
            }
            tmp.add(cur);
            backTrack(i);
            tmp.remove(tmp.size()-1);
        }
    }

    @Test
    public void t(){
        List<List<String>> res = partition("aab");
        System.out.println("res=" + res);
    }
}
